package MiddlePractice;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Demo210 {
//	210. 课程表 II
//	现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
//
//	例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
//	返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
	
	private boolean hasCircle = false;
    private boolean[] path;
	private boolean[] visited;
	private List<Integer>[] graph;
	private List<Integer> postorder = new LinkedList<>();
	
	public int[] findOrder(int numCourses, int[][] prerequisites) {
		graph = new List[numCourses];
        for(int i = 0 ; i<numCourses; i++) {
			graph[i] = new LinkedList<>();
		}
		graph = createGraph(numCourses, prerequisites);
		
		if(!canFinish(numCourses, prerequisites)) {
			int[] res = {};
			return res;
		}
		
		for(int i=0; i<numCourses; i++) {
			DFS(graph, i);
		}
		
		LinkedList<Integer> stack = new LinkedList<>();
		Iterator it =  postorder.iterator();
		while(it.hasNext()) {
			stack.push((Integer)it.next());
		}
		
		int[] result = new int[numCourses];
		int i =0;
		while(!stack.isEmpty()) {
			result[i++] = stack.pop();
		}
		
		return result;
    }
	
	//建图函数  输出List<Integer>[]
	private List<Integer>[] createGraph(int numCourses, int[][] prerequisites){
		for(int i = 0 ; i<numCourses; i++) {
			graph[i] = new LinkedList<>();
		}
		
		for(int i = 0 ; i<prerequisites.length; i++) {
			int to = prerequisites[i][0];
			int from = prerequisites[i][1];
			graph[from].add(to);
		}
		return graph;
	}
	
	private boolean canFinish(int numCourses, int[][] prerequisites) {
		List<Integer>[] graph = createGraph(numCourses, prerequisites);
		visited = new boolean[numCourses];
		path = new boolean[numCourses];
		for(int i=0; i<numCourses; i++) {
			DFS(graph, i);
		}
		
		return !hasCircle;
    }
	
	private void DFS(List<Integer>[] graph, int vex) {
		if(path[vex]){
            hasCircle = true;
        }
        
        if(visited[vex] || hasCircle) {
			
			return;
		}
		
		visited[vex] = true;
        path[vex] = true;
		for(Integer neighbor : graph[vex]) {
			DFS(graph, neighbor);
		}
		
		//回溯前处理
		path[vex] = false;
		postorder.add(vex);
	}
}
